This invention relates to methods of operating digital computers and, more particularly, to a method of operating a plurality of digital processors to solve enumerative search, graph search or combinatorial optimization problems.
Practical enumerative search, graph search or combinatorial optimization problems occur in a variety of fields including various engineering disciplines, management and econometrics. Such problems are characterized in that their solution consists of identifying the optimum combination of individual choice selections from among a multitude of possibilities. Examples of such enumerative search, graph search or combinatorial optimization problems include: determining the best move in a game of chess or checkers, determining which articles of different values and sizes should be packed into a container of limited capacity in order to maximize the total value of the container's contents, and determining the optimum scheduling of operations in a manufacturing facility to maximize profitability.
In principle, such enumerative search, graph search or combinatorial optimization problems can be solved by testing all possible combinations of choices against each other and selecting the combination giving the most favorable result. However, in anything other than the most simple problems, the number of possible combinations or choices rapidly becomes so large that, even when digital computers are employed, the solution of a single problem on a single processor might take hours or many days. Although such a delay might be unimportant when the problem conditions are stable and the solution to a particular problem can be worked out well in advance of actual need, a number of practical situations require that a solution be determined quickly in the face of rapidly changing data. For example, determining the optimum launch schedules for surface-to-air missile engagements in naval anti-air craft warfare requires that a solution be determined in the brief interval between the initial detection, and final arrival, of enemy forces.
One known approach to reducing the time required to solve an enumerative search, graph search or combinatorial optimization problem involves the use of several computers or "parallel processors" working simultaneously to solve the problem. In theory, a problem taking 24 hours to solve on a single processor, for example, should be solvable in 1 hour using 24 parallel processors. In practice, however, the need to provide for communication and/or other coordination between individual processors limits how much actual, additional, problem solving ability or capacity each processor can bring to bear on the problem. Typically, as the size of the problem and the number of processors grows, more and more time is taken up for communications, synchronization of processors, starting up processors, and, searching, unecessarily, certain solution paths. Thus, the marginal utility of each additional processor drops until an upper limit on actual problem solving capacity is reached, i.e., at some point the full capacity of each additional processor is needed entirely for "overhead" purposes, and no additional problem solving capacity is added to the system as a whole. This effectively limits the speed with which a problem of given size can be solved.
Numerous parallel processor architectures based on a wide spectrum of design philosophies have been developed and sold. However, there is presently no commercially available hardware and/or software for solving general enumerative search problems in a multiprocessor environment. Software systems designed to run on specific processor architectures for solving specialized enumerative search, graph search or combinatorial optimization problems have appeared. These systems are designed specifically for solving integer programs on BBN Butterfly equipment and solving logic programs (e.g., Prolog). None of the techniques and/or approaches are in any way related to the techniques which form the basis for the present invention.
Numerous hardware/software systems and machines have been either developed or proposed within the academic community for solving specialized cases of enumerative search, graph search or combinatorial optimization algorithms in a multiprocessor environment. As in the case of the commercially available products, these systems are usually adapted to the particular subclass of problems that is being addressed. Recently, work has been published, and hardware/software systems, techniques and methodologies have been developed, for general combinatorial optimization problems. This appears to be a growth area in the academic community, but no commercial products resulting from this work have appeared to date. Results reported from these studies indicate, however, that these approaches do not achieve the same level of generality as the present invention. Also, for most previous approaches to this problem, the marginal utility rapidly approaches zero for added loosely coupled processors for a fixed size problem, thereby imposing an absolute limit on the size of the problem that can be treated.
In view of the foregoing, it is a general object of the present invention to provide a new and improved method and apparatus for operating parallel digital processors to solve enumerative search, graph search or combinatorial optimization problems.
It is a further object of the present invention to provide a new and improved method of operating parallel digital processors that is general in its applicability and effectiveness and can thus be used to solve a wide range of enumerative search, graph search or combinatorial optimization problems.
It is a still further object of the present invention to provide a method of operating parallel digital processors to solve enumerative search, graph search or combinatorial optimization problems wherein each processor, regardless of how many, provides at least a minimum marginal utility so that an enumerative search, graph search or combinatorial problem of any given size can be solved within any non-zero time period through the addition of an appropriate number of processors.